/*
 * Copyright (C), 2015-2018
 * FileName: Solution016
 * Author:   zhao
 * Date:     2018/11/10 23:04
 * Description: 16. 最接近的三数之和
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.mid;

import java.util.Arrays;

/**
 * 〈一句话功能简述〉<br>
 * 〈16. 最接近的三数之和〉
 *
 * @author zhao
 * @date 2018/11/10 23:04
 * @since 1.0.1
 */
public class Solution016 {

    /**************************************
     * 题目

     给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

     例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

     与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
     **************************************/

    /**************************************
     *
     * 想法：
     *      1. 暴力破解法：
     *          循环三轮
     *      2. 使用前面三数之和的逻辑
     *          排序数组
     *          以第一个数为起点，后面2数进行滑动列表操作
     *
     * 我的做法
     *      超过99%的测试案例
     *      时间复杂度：n2
     *      空间复杂度：1
     * 代码执行过程：
     *
     * 总结：
     *
     * ***********************************/
    public int threeSumClosest(int[] nums, int target) {

        if (nums == null || nums.length < 3) {
            return 0;
        }
        Arrays.sort(nums);

        int comp = Integer.MAX_VALUE;
        int result = Integer.MAX_VALUE;

        for (int i = 0; i < nums.length; i++) {
            // 如果和之前那个数据相同，则会是重复事件
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int leftIndex = i + 1;
            int rightIndex = nums.length - 1;

            // 滑动列表
            while (leftIndex < rightIndex) {
                int tmp = nums[leftIndex] + nums[rightIndex] + nums[i];
                if (comp > Math.abs(tmp - target)) {
                    comp = Math.abs(tmp - target);
                    result = tmp;
                }

                if (tmp > target) {
                    rightIndex--;
                } else if (tmp < target) {
                    leftIndex++;
                } else {
                    // 差值为0，最爽了，直接返回
                    return tmp;
                }
            }
        }
        return result;
    }

    /**
     * 暴力破解
     * 超过5%的测试案例
     * 时间复杂度：n3
     * 空间复杂度：1
     *
     * @param nums   数组
     * @param target 目标值
     * @return 结果
     */
    public int threeSumClosestByBrute(int[] nums, int target) {
        if (nums == null || nums.length < 3) {
            return 0;
        }

        int comp = Integer.MAX_VALUE;
        int result = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    int tmp = nums[i] + nums[j] + nums[k];
                    if (comp > Math.abs(tmp - target)) {
                        comp = Math.abs(tmp - target);
                        result = tmp;
                    }
                }
            }
        }

        return result;
    }

    /**************************************
     * 比我好的答案 better
     * ***********************************/
    public int better(int[] nums, int target) {

        int result = nums[0] + nums[1] + nums[2];
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            int start = i + 1, end = nums.length - 1;

            while (start < end) {
                int tmpSum = nums[i] + nums[start] + nums[end];
                if (Math.abs(tmpSum - target) < Math.abs(result - target)) {
                    result = tmpSum;
                }
                if (tmpSum < target) {
                    start++;
                } else if (tmpSum > target) {
                    end--;
                } else {
                    return result;
                }

            }
        }
        return result;
    }

}
